package features.advance.edu.compilers.regex;

import features.advance.leetcode.tree.model.StringTreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author LIN
 * @date 2022-01-30 09:11
 */
public class Demo {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        String normal = "(a|b)*.a.b.b";
        Queue<Character> back = solution.getRegBack(normal);
        System.out.println(back);

        String expression = "a+b-c";
        Queue<Character> expBack = solution.getExpBack(expression);
        System.out.println(expBack);
        Stack<String> backOprExp = solution.getBackOprExp(expression);
        System.out.println(backOprExp);

        StringTreeNode root = new StringTreeNode("-");
        StringTreeNode node1 = new StringTreeNode("+");
        StringTreeNode node2 = new StringTreeNode("a");
        StringTreeNode node3 = new StringTreeNode("b");
        StringTreeNode node4 = new StringTreeNode("c");
        root.left = node1;
        root.right = node4;
        node1.left = node2;
        node1.right = node3;
        TreeUtil.cenorder(root);
        System.out.println();
        TreeUtil.postorder(root);
        System.out.println();



    }

    static class Solution {
        /**
         * 获取公式的后缀表达式，公式本身就是个树的中缀表达式
         * @param exp
         * @return
         */
        public Stack<String> getBackOprExp(String exp) {
            Stack<String> s1 = new Stack<>();
            Stack<String> s2 = new Stack<>();
            try {
                char[] c = exp.toCharArray();
                StringBuilder buf = new StringBuilder();
                for (int i=0; i<c.length; i++) {
                    if (c[i] == ' ') {
                        continue;
                    } else if ("+-*/()".indexOf(c[i]) < 0) {
                        buf.append(c[i]);
                    } else {
                        if (buf.length() > 0) {
                            s1.push(buf.toString());
                            buf.delete(0,  buf.length());
                        }
                        switch (c[i]) {
                            case '+':
                            case '-':
                                while(s2.size() > 0 && "*/".contains(s2.peek())) {
                                    s1.push(s2.pop());
                                }
                                s2.push(String.valueOf(c[i]));
                                break;
                            case '*':
                            case '/':
                            case '(':
                                s2.push(String.valueOf(c[i]));
                                break;
                            case ')':
                                while (s2.size() > 0 && !"(".equals(s2.peek())) {
                                    s1.push(s2.pop());
                                }
                                s2.pop();
                                break;
                        }
                    }
                }
                if (buf.length() > 0) {
                    s1.push(buf.toString());
                }
                while (s2.size() > 0) {
                    s1.push(s2.pop());
                }
                while (s1.size() > 0) {
                    s2.push(s1.pop());
                }
            } catch (Throwable e) {
                e.printStackTrace();
            }

            return s2;
        }

        /**
         * 中缀表达式转成后缀表达式
         * @param expression
         * @return
         */
        public Queue<Character> getExpBack(String expression){
            // queue用于存放计算后得到的后缀表达式
            Queue<Character> queue = new LinkedList<>();
            // stack用于存放过程中的操作符
            Stack<Character> stack = new Stack<>();
            // list作为字母表
            LinkedList<String> list = new LinkedList<>();

            for (int i = 0; i < expression.length(); i++) {
                char m = expression.charAt(i);
                // 不是(，)，*，|，.，+
                if(m != '(' && m != ')' && m != '*' && m != '/' && m != '-' && m != '+'){
//                    if(!list.contains(""+m)){
//                        list.add(""+m);
//                    }
                    queue.add(m);
                    // 字符是)
                }else if(m == ')'){
                    char n = stack.pop();
                    // 一直读取，直到找到左小括号
                    while (n != '('){
                        queue.add(n);
                        n = stack.peek();
                    }
                    stack.pop();
                }else if(m == '*'){
                    queue.add(m);
                }else{
                    stack.push(m);
                }
            }
            while (!stack.isEmpty()){
                if(stack.peek() != '('){
                    queue.add(stack.pop());
                }else{
                    stack.pop();
                }
            }


            return queue;
        }

        public Queue<Character> getRegBack(String normal){
            // queue用于存放计算后得到的后缀表达式
            Queue<Character> queue = new LinkedList<>();
            // stack用于存放过程中的操作符
            Stack<Character> stack = new Stack<>();
            // list作为字母表
            LinkedList<String> list = new LinkedList<>();
            // 按顺序读取字符串里的字符
            for (int i = 0; i < normal.length(); i++) {
                // 当前位置的字符
                char m = normal.charAt(i);
                // 不是(，)，*，|，.，+
                if(m != '(' && m != ')' && m != '*' && m != '|' && m != '.' && m != '+'){
                    if(!list.contains(""+m)){
                        list.add(""+m);
                    }
                    queue.add(m);
                    // 字符是)
                }else if(m == ')'){
                    char n = stack.pop();
                    // 一直读取，直到找到左小括号
                    while (n != '('){
                        queue.add(n);
                        n = stack.peek();
                    }
                    stack.pop();
                }else if(m == '*'){
                    queue.add(m);
                }else{
                    stack.push(m);
                }
            }
            // 栈不是空的，先进后出
            while (!stack.empty()) {
                if(stack.peek() != '('){
                    queue.add(stack.pop());
                }else{
                    stack.pop();
                }
            }
            return queue;
        }
    }
}
